package com.berchen.数据结构.二叉树.赫夫曼树;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 赫夫曼树
 * 赫夫曼树就是带权路径长度最短的树，权值较大的节点离根节点较近。
 * 叶子节点的带权路口长度之和最小的树就是赫夫曼树。
 *
 * 如何创建赫夫曼树？
 * 【13,7,8,3,29,6,1】
 * 将数组从小到大进行排序。
 * 取出数组中第一第二的数，
 * 组合成一个新的二叉树。
 * 再将这个二叉树的根节点的权值放入数据中进行排序。
 * 重复上面操作。
 *
 *
 */
public class HuffmanTree {

    public static void main(String[] args) {

        int[] arr={13,7,8,3,29,6,1};
        innOrder(createHuffman(arr));

    }

    /**
     * 中序遍历赫夫曼树  只打印叶子节点
     * @param node
     */
    public static void innOrder(TreeNode node){
        if(node==null){
            System.out.println("赫夫曼树为null");
        }
        if(node.left!=null){
            innOrder(node.left);
        }
        if(node.left==null&&node.right==null){
            System.out.println(node.toString());
        }
        if(node.right!=null){
            innOrder(node.right);
        }
    }

    /**
     * 创建赫夫曼树
     * @param arr
     * @return
     */
    public static TreeNode createHuffman(int arr[]){

        List<TreeNode> nodes=new ArrayList<>();
        for(int i=0;i<arr.length;i++){
            nodes.add(new TreeNode(arr[i]));
        }

        while (nodes.size()>=2){

            Collections.sort(nodes);
            // 取出第一第二两个元素
            TreeNode leftNode=nodes.get(0);
            TreeNode rightNode=nodes.get(1);

            TreeNode root=new TreeNode(leftNode.value+ rightNode.value);
            root.left=leftNode;
            root.right=rightNode;
            // 删除集合中的刚取出的两个节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(root);
        }
        // 返回赫夫曼树的跟节点
        return nodes.get(0);
    }
}
